﻿using System;
using Algoritmia.Utils;
using Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Searching
{
    public class RecursiveBinarySearcher<T> : ISortedSearcher<T>
    {
        private Comparison<T> _comparison;


        #region ISortedSearcher<T> Members

        public int IndexOf(IList<T> list, T elem, Comparison<T> comparison = null)
        {
            _comparison = AlgoritmiaFactory.GetDefaultComparison(comparison);
            Func<int, int, int> f = null;
            f = (first, last) =>
                    {
                        int pivot = (first + last) / 2;

                        if (_comparison(elem, list[pivot]) < 0)
                        {
                            last = pivot;
                        }
                        else if (_comparison(elem, list[pivot]) > 0)
                        {
                            first = pivot + 1;
                        }
                        else
                        {
                            return pivot;
                        }

                        if (first == last) return _comparison(list[first], elem) == 0 ? first : -1;

                        return f(first, last);
                    };
            return f(0,list.Count-1);
        }

        #endregion
    }
}
